package com.xuxiang.cloud.java.defcode.sort;

/**
 * @author xuxiang 2018/10/25 16:03
 */
public class QuickSort implements Sort {

    @Override
    public void sort(int[] arr, int from, int to) {

        if (from >= to) {
            return;
        }
        int pos = pos(arr, from , to);
        sort(arr, from, pos - 1);
        sort(arr, pos + 1, to);
    }

    private int pos1(int[] arr, int from, int to) {
        int v = arr[from];
        int i = from ;
        int j = to;
        while (i < j) {
            while (i < j && arr[j] >= v) {
                j--;
            }
            arr[i] = arr[j];
            while (i < j && arr[i] <= v) {
                i++;
            }
            arr[j] = arr[i];
        }
        arr[i] = v;
        return i;
    }

    private int pos(int[] arr, int from, int to) {
        int v = arr[to];
        int i = from - 1;
        for (int j = i + 1; j < to ; j++) {
            if (arr[j] < v) {
                swap(arr, ++i, j);
            }
        }
        swap(arr, ++i, to);
        return i;
    }

    private void swap(int [] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
